1. Field of the Invention
The present invention relates to a computer system, and deals more particularly with a method, system, and computer-readable code for embedding a file index within a data file to which the index pertains.
2. Description of the Related Art
File indexing is well known in the computer art, and provides a technique for randomly accessing data from a file in order to locate data in the file more quickly than would be possible using a sequential search. A file index typically consists of entries containing (1) some type of key value that enables identifying a particular record in the file, and (2) an address that can be used to locate that record on a storage medium. Records in the file are then accessed by searching the index using the key value, and retrieving the associated record address. The key value used may be a value that is uniquely associated with, and forms a part of, each record from the file (such as an employee number in a file of employee records). Or, the key value may be computed using a mathematical algorithm to generate a result that is uniquely associated with a file record. This key generation technique is referred to as xe2x80x9chashingxe2x80x9d, and many approaches to hashing are known in the art.
Many different approaches to structuring file indexes are also known in the art. Different structures provide different time estimates for average record retrieval, insertion, and deletion, as well as best case and worst case time estimates. One such index structure is a hash table, which is used with the hashed key values discussed above. Or, various tree structures may be used for a file index. When using a tree structure, each node of the tree typically contains some number of key values and other information related to the keys. As an example of the type of other information, some nodes will contain pointers that must be traversed further when searching for a particular key; other nodes will contain the record address for the record associated with that key (or a pointer to the stored record). Types of tree-structured indexes known in the art include B-trees, tries, B*-trees, and Bxe2x80x2-trees. Differences among these tree structures include: how many key values can be stored in a node, whether full or partial keys are stored in the nodes, and whether record addresses are stored in intermediate nodes or only in leaf nodes of the tree. (The specific details of implementing these various tree structures, and advantages thereof, may be found in a data structures reference such as Chapters 7 and 8 of xe2x80x9cAlgorithms and Data Structures in C++xe2x80x9d, Leendert Ammeraal, published by John Wiley and Sons (1996).)
Random-access files are typically stored on a persistent storage medium such as a disk drive. When an executing program needs to access a record located in the file, a portion of the stored disk file containing the record is read into memory. (Typically, a xe2x80x9cpagexe2x80x9d of data is read into memory, where a page is 4096 bytes of data.) If the record is updated by the executing program, then the changed information must be rewritten to persistent storage when the updates are complete. The changed information may be rewritten in the same location where the prior version of the record was stored, or it may be written to a new location. (For example, if the updated record is now larger than the version it replaces, it may be necessary to move the record to a new storage area that can accommodate the larger record.) Moving the location of the record requires changing the record address information in the file index. When a record is to be added to a file, a file manager facility is consulted to locate available free space within the file. The new information is written into an area allocated by the file manager, and an entry for this new record is created in the file index. When a record is to be deleted from a file, the file manager deallocates the file space the record was using, and the entry for the deleted record must be removed from the index. These concepts are known in the art, and file management facilities are readily available.
As can be seen from the discussion above, making changes to records stored in a file (whether through updates, additions, or deletions) requires not only changing the stored record but also typically requires changes to the file index. A file and its index must be kept precisely synchronized as these changes occur, to preserve the integrity of the data. For example, suppose a record is to be deleted from a file. If the deletion completes successfully, but some type of error condition (such as a system failure due to hardware and/or software problems) occurs before the corresponding key is removed from the index, the index no longer accurately represents the stored file. Similarly, if a data record is added to a file but the index is not properly updated with the new record""s key, the files are not synchronized and it is not possible to locate the new record using the index. Because updating a file on persistent storage is normally an expensive operation in terms of computing time, file revisions are typically made in a batch mode. In this approach, a number of revised records are kept in faster memory storage until some point in time, and then the entire group or batch of revisions is written to the persistent store at the same time. While this batch approach minimizes the overhead required for revising records, the higher number of records involved results in an increase in the potential for inconsistencies between the data file and its index, should an error occur. Known solutions for dealing with these types of data integrity problems include using transaction processing techniques, where the updating of both the data file and the index file is treated as a single atomic transaction. The updates are only xe2x80x9ccommittedxe2x80x9d (i.e. made permanent) to the persistent store if the entire update process completes successfully; otherwise, the updates to both the data file and the index are xe2x80x9crolled backxe2x80x9d (i.e. discarded) as a group.
Providing program logic to detect and/or recover from a mismatch between a data file and its index is complex and error-prone. However, inefficiencies in program operation when storing a file and its index separately may occur even in the absence of error conditions. For example, separate allocation requests must be made when creating a data file and its index file. Similarly, when the file is no longer needed, separate deallocation requests must be made for the file and its index. Further, the separate physical locations of the data file and its index on the storage medium may cause processing inefficiencies. This is because accessing an index by an executing program is closely tied to accessing the corresponding data file: normally when a record update or retrieval occurs, the index is accessed and then the data file is accessed. This sequence is then repeated for the next record update or retrieval. If the data file is not stored physically near the index, the storage medium may exhibit thrashing behavior as the read/write mechanism moves back and forth between the two storage areas. Further, if the record address stored in the index is returned to a program, compaction of the data file (so that all unallocated blocks will be located at the end, for example) becomes complicated and error-prone because it may not be possible to determine when such record addresses cease being used by the program. Compaction of the data file requires rebuilding its associated index, so that a record""s key entry will then be associated with its new location. If a program continues using a record address that it received prior to the compaction process, it will likely be referring to data other than what it expects (with a high probability of program failure as a result).
Accordingly, what is needed is a technique which avoids the problems discussed above. The present invention addresses these problems by providing a novel solution whereby a file index is embedded within the data file to which it corresponds.
An object of the present invention is to provide a technique whereby a data file can efficiently remain synchronized with its corresponding index.
Another object of the present invention is to provide a technique whereby data integrity between a data file and its index is automatically preserved when a file checkpoint succeeds, and recovery/restart complexity is minimized.
Still another object of the present invention is to provide a technique whereby physical access time for accessing data file records in persistent storage is minimized.
It is another object of the present invention to provide a technique whereby data file compaction can occur with minimal risk of inaccurate location references by executing programs.
Yet another object of the present invention is to provide these benefits by embedding a file index within the data file to which it corresponds.
Other objects and advantages of the present invention will be set forth in part in the description and in the drawings which follow and, in part, will be obvious from the description or may be learned by practice of the invention.
To achieve the foregoing objects, and in accordance with the purpose of the invention as broadly described herein, the present invention provides a software-implemented process, a system, and a method for use in a computing environment, for increasing efficiency of indexing random-access files. This technique comprises: storing data records in a random-access file, where the file comprises a control area and a plurality of fixed-length block and wherein each of the data records is stored as one or more of the fixed-length blocks; creating an embedded index for the file, wherein the index is stored as one or more of the fixed-length blocks; updating the index; and using the index to retrieve a selected one of the stored records. This technique may further comprise: allocating an index control area for the index within the control area of the random-access file; and storing an address of the index in the index control area. Preferably, the process of updating the index is invoked each time the storing process completes successfully, and the process of updating the index further comprises: computing a key value for the data record; storing the computed key value in a key object; storing an address where the data record was stored in the key object; and inserting the key object into the index; and the technique further comprises deleting the stored data record from the file if the inserting step encounters an error. Using the index step preferably further comprises: comparing selected ones of the inserted key objects to a record key of the selected record; returning a not-found indication when none of the selected key objects contains the record key; and reading the selected record from the random-access file using the stored address in a matching one of the selected key objects when the matching one contains the record key. The technique may further comprise deleting a particular record from the random-access file, which further comprises: removing an associated key object from the index; and deallocating one or more blocks associated with the particular record. The index may be a tree-structured index, which may be a B-Tree index. In an optional aspect, the technique may further comprise: creating a first write-prepare record to store information related to the storing; creating a second write-prepare record to store information related to the updating; storing the first and second write-prepare records in a persistent prepare store; resetting the prepare store when the storing and updating complete successfully; and restoring the file when a file error occurs. In another optional aspect, the technique may further comprise: creating a first delete-prepare record to store information related to the deallocating; creating a second delete-prepare record to store information related to the removing; storing the first and second delete-prepare records in a persistent prepare store; resetting the prepare store when the deallocating removing complete successfully; and restoring the file when a file error occurs.
The present invention will now be described with reference to the following drawings, in which like reference numbers denote the same element throughout.